package history.study.dynamic_programming;

// 63. 不同路径 II
/**
 *  1. dp[i][j] 为到达(i,j)有多少种方式
 *  2. 递推公式：dp[i][j] = dp[i-1][j]+dp[i][j-1]
 *  3. dp[i][0] = 1, dp[0][j] = 1
 *  4. 从前往后进行遍历
 *  5. dp[3][3] = dp[2][3]+dp[3][2]
 *     dp[4][4]= dp[3][4]+dp[4][3]
 */
public class LeetCode_63 {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid.length <0 || obstacleGrid[0].length < 0) return 0;
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        boolean m0 = false, n0 = false;
        int [][]state = new int[m][n];
        for (int i = 0; i < m; i++) {
            if (!m0 && obstacleGrid[i][0] != 1) {
                state[i][0] =1;
            } else {
                state[i][0] = 0;
                m0 = true;
            }
        }
        for (int i = 0; i < n; i++) {
            if (!n0 && obstacleGrid[0][i] != 1) {
                state[0][i]  = 1;
            } else {
                state[0][i] = 0;
                n0 = true;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 1) {
                    state[i][j] = 0;
                } else {
                    state[i][j] = state[i-1][j]+state[i][j-1];
                }
            }
        }
        return state[m-1][n-1];
    }
}
